In general, schedulers manage when to allocate system resources to service different tasks. When employed in router applications, schedulers manage many queues and ensure overall fairness of outputting data packets from the queues by selectively servicing queues at different times. Queues are sometimes guaranteed at least a minimal rate of outputting data. Consequently, it is important to service such queues often enough so that the queue outputs data at the corresponding guaranteed rate and the queues do not become congested with data.
One implementation of a scheduler is a calendar. Calendars schedule servicing of tasks in real-time by maintaining linked lists. Each linked list includes task entries that are to be serviced in a particular time slot of the calendar. As a real-time clock advances, tasks stored as entries in the linked lists are serviced. In one application, scheduled tasks includes servicing one or more queues.
A linked list typically includes a head pointer, a tail pointer and next pointers. Thus its size is almost entirely determined by how many things it contains. A calendar is an array of linked lists. Thus, a calendar consumes space for a head and tail pointer for each slot it maintains. In one application, a calendar including 256 slots includes 256 head pointers and 256 tail pointers. If each pointer is 2 bytes, the 256 slot calendar consumes 1 Kilobyte. If a scheduler maintains 100 such calendars for scheduling independent tasks, then 100 kilobytes of memory is required to maintain these calendars.
In the context of a router application, it is not uncommon to schedule over thirty thousand independent groups of (tasks) queues for servicing. Maintaining many calendars is sometimes inefficient. For example, if hundreds of thousands of queues divided into 32,000 groups, there is a need for 32,000 calendars. Consequently, this would require 32 Megabytes of storage (e.g., at 1 Kilobyte per calendar). If the calendars are more granular and include 1024 slots each, such a system of 32,000 calendars consumes 256 Megabytes.
Another implementation of a scheduler is a sorting tree such as a heap or a B-tree. In these applications, tasks are scheduled for servicing based on their relative priority, which indicates precedence in an arbitrarily complex service ordering. For example, an entry at a highest root node of the tree stores a highest priority task for servicing. After servicing the highest priority task, the tree is updated so that the next highest priority task moves to the highest root node of the tree.